package com.sx.sx1.lintcode.day919;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LC677 {

    static class Solution {
        /**
         * @param grid: a 2d boolean array
         * @param k:    an integer
         * @return: the number of Islands
         */
        public int numsofIsland(boolean[][] grid, int k) {
            int n = grid.length;
            int m = grid[0].length;

            UF uf = new UF();

            for (int i = 0; i <n ; i++) {
                for (int j = 0; j <m ; j++) {
                    if(grid[i][j]) {
                        dfs(grid,i,j,i*m+j,uf);
                    }
                }
            }

            int ans =0;
            for(int mk: uf.size.keySet()){
                if(uf.size.get(mk) >=k){
                    ans++;
                }
            }
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < m; j++) {
//                    if( uf.size.containsKey(i*m+j) &&uf.size.get(i*m+j)!=0)  System.out.println("new:"+ (i*m+j)+" " + uf.size.get(i*m+j));
//                }
//            }

            return ans;
        }

        public void dfs(boolean[][] grid,int i,int j,int pid,UF uf){
            int n = grid.length;
            int m = grid[0].length;
            if(i<0 || i==n || j<0 || j ==m || !grid[i][j] )
                return;
            grid[i][j] = false;
            int curidx = i*m+j;
            uf.union(pid,curidx);
            dfs(grid,i-1,j,pid,uf);
            dfs(grid,i+1,j,pid,uf);
            dfs(grid,i,j-1,pid,uf);
            dfs(grid,i,j+1,pid,uf);
        }


        static class UF { //并查集的类，下面三个map变量可以用数组来做
            public Map<Integer, Integer> parents = new HashMap<>();
            public Map<Integer, Integer> size = new HashMap<>();
            public Map<Integer, Integer> help = new HashMap<>();

            public int sets =0;
            public UF() {
            }

            public int find(int x) { //并查集的路径压缩
                if(!parents.containsKey(x)){
                    parents.put(x,x);
                    size.put(x,1);
                    sets++;
                }
                int hi = 0;
                while (x != parents.get(x)) {
                    help.put(hi++, x);
                    x = parents.get(x);
                }

                for (hi--; hi >= 0; hi--) {
                    parents.put(help.get(hi), x);
                }
                return x;
            }



            public void union(int a,int b) {//并查集的合并

                int f1 = find(a);
                int f2 = find(b);

                if (f1 != f2) {
                    int s1 = size.get(f1);
                    int s2 = size.get(f2);
                    int s = s1 + s2;

                    if (s1 >= s2) {
                        size.put(f1, s);
                        parents.put(f2, f1);
                    } else {
                        size.put(f2, s);
                        parents.put(f1, f2);
                    }
                    sets--;
                }
            }
        }
    }


    public static void main(String[] args) {
        int[][] arr = {{1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}};
        boolean[][] arr1 = new boolean[arr.length][arr[0].length];
        boolean[][] arr2 = new boolean[arr.length][arr[0].length];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                arr1[i][j] = arr[i][j] == 1 ? true : false;
                arr2[i][j] = arr[i][j] == 1 ? true : false;
            }
        }

      int ans=  new Solution().numsofIsland(arr1, 2);
        System.out.println(ans);

        new Solutionold().numsofIsland(arr2, 2);
    }


    static class Solutionold {
        /**
         * @param grid: a 2d boolean array
         * @param k:    an integer
         * @return: the number of Islands
         */
        public int numsofIsland(boolean[][] grid, int k) {
            // Write your code here
            return fun1(grid, k);
        }


        public int fun1(boolean[][] arr, int k) {
            int n = arr.length;
            int m = arr[0].length;

            UF uf = new UF(arr);

            for (int i = 1; i < m; i++) {//处理第一行
                if (arr[0][i - 1] && arr[0][i]) {
                    uf.union(0, i - 1, 0, i);
                }
            }

            for (int i = 1; i < n; i++) {//处理第一列
                if (arr[i - 1][0] && arr[i][0]) {
                    uf.union(i - 1, 0, i, 0);
                }
            }

            //普遍位置处理
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < m; j++) {
                    if (arr[i][j - 1] && arr[i][j]) {
                        uf.union(i, j - 1, i, j);
                    }

                    if (arr[i - 1][j] && arr[i][j]) {
                        uf.union(i - 1, j, i, j);
                    }
                }
            }

            for (int i = 0; i < uf.size.length; i++) {
               if(uf.size[i]!=0) System.out.println("old: " + i + " " + uf.size[i]);
            }

            return uf.topk(k);
        }

        static class UF {
            public int[] parent;
            public int[] size;
            public int[] help;
            public int cols;
            public int sets;

            public UF(boolean[][] arr) {
                int row = arr.length;
                cols = arr[0].length;
                int all = row * cols;
                parent = new int[all];
                size = new int[all];
                help = new int[all];

                for (int i = 0; i < row; i++) {
                    for (int j = 0; j < cols; j++) {
                        if (arr[i][j]) {
                            int index = index(i, j);
                            parent[index] = index;
                            size[index] = 1;
                            sets++;
                        }
                    }
                }
            }

            public int index(int r, int c) {
                return r * cols + c;
            }

            public int find(int index) { //并查集，路径压缩
                int hi = 0;
                while (index != parent[index]) {
                    help[hi++] = parent[index];
                    index = parent[index];
                }

                for (hi--; hi >= 0; hi--) {
                    parent[help[hi]] = index;
                }

                return index;
            }

            public void union(int a, int b, int c, int d) {
                int i1 = index(a, b);
                int i2 = index(c, d);

                int f1 = find(i1);
                int f2 = find(i2);

                if (f1 != f2) {
                    if (size[f1] >= size[f2]) {
                        size[f1] = size[f1] + size[f2];
                        parent[f2] = f1;
                    } else {
                        size[f2] = size[f1] + size[f2];
                        parent[f1] = f2;
                    }
                    sets--;
                }
            }

            public int topk(int k) {
                Set<Integer> s = new HashSet<>();
                for (int index : parent) {
                    if (index == parent[index] && size[index] >= k) {
                        s.add(index);
                    }
                }

                return s.size();
            }
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有195条未读消息，请及时查看
677 · 大岛的数量
算法
中等
通过率
45%

题目
题解21
笔记
讨论61
排名
记录
描述
给一个布尔类型的二维数组, 0 表示海, 1 表示岛。如果两个1是相邻的,那么我们认为他们是同一个岛.我们只考虑 上下左右 相邻.

找到大小在 k 及 k 以上的岛屿的数量。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例1

输入：
[[1,1,0,0,0],[0,1,0,0,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,0,0,1]]
2
输出： 2
解释：
2D网络为
[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]
一共有 3 个岛屿，其中两个岛屿大小为 3，另一个大小为 1（小于 k(2)），故返回 2。
样例2

输入：
[[1,0],[0,1]]
1
输出： 2
标签
相关题目

433
岛屿的个数
简单

434
岛屿的个数II
中等

804
不同岛屿的数量II
困难
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
已开启智能提示
发起考试
30 分 00 秒
12345678910

控制台
        历史提交

 */
